#include<stdio.h>
#include<time.h>
#include<stdlib.h>
long i,j,tep,f;
long maopao();
long xuanzhe();
long charu();
int get_mid(int d[], int lift, int right);
void quick_sort(int d[], int left, int right);
long kuaisu();
long maopao()
{
	int a[100000] = {0};
	srand(time(NULL));
	for(i = 0; i < 100000; i++)
	{
		a[i] = random();
	}
	long start_maopao,end_maopao;
	time(&start_maopao);
	for(i = 0; i < 99999; i++)
	{
		f = 0;
		for(j = 0; j < 99999 - i; j++)
		{
			if(a[j] > a[j + 1])
			{
				tep = a[j + 1];
				a[j + 1] = a[j];
				a[j] = tep; 
				f = 1;	
			}
		}
		if(f == 0)
		{
			break;
		}
	}
	time(&end_maopao);
	printf("冒泡排序前五个数排序测试：\n");
	for(i = 0; i < 5; i++)
	{
		printf("%d\n",a[i]);
	}
	return end_maopao - start_maopao;
}
long xuanzhe()
{
	int b[100000] = {0};
	srand(time(NULL));
	for(i = 0; i < 100000; i++)
	{
		b[i] = random();
	}
	long start_xuanzhe,end_xuanzhe;
	time(&start_xuanzhe);
	for(i = 0; i < 99999; i++)
	{
		f = i;
		for(j = i + 1; j < 100000; j++)
		{
			if(b[f] > b[j])
			{
				f = j;
			}
		}
		if(f != i)
		{
			tep =  b[i];
			b[i] = b[f];
			b[f] = tep;
		}
	}
	time(&end_xuanzhe);
	printf("选择排序前五个数排序测试：\n");
	for(i = 0; i < 5; i++)
	{
		printf("%d\n",b[i]);
	}
	return end_xuanzhe - start_xuanzhe;
}
long charu()
{
	int c[100000] = {0};
	srand(time(NULL));
	for(i = 0; i < 100000; i++)
	{
		c[i] = random();
	}
	long start_charu, end_charu;
	time(&start_charu);
	for(i = 1; i < 100000; i++)
	{
		f = 0;
		tep = c[i];
		for(j = i - 1; tep < c[j] && j >= 0; j--)
		{
			c[j + 1] = c[j];
			f = 1;
		}
		if(f == 1)
		{
			c[j + 1] = tep;
		}		
	}
	time(&end_charu);
	printf("插入排序前五个数排序测试：\n");
	for(i = 0; i < 5; i++)
	{
		printf("%d\n",c[i]);
	}
	return end_charu - start_charu;
}
int get_mid(int d[], int left, int right)
{
	int pivot = d[left];
	while(left < right)
	{
			while(d[right] > pivot && left < right)
			{
				right--;
			}
			d[left] = d[right];
			while(d[left] <= pivot && left < right)
			{
				left++;
			}
			d[right] = d[left];
	}
	d[left] = pivot;
	return left;
}
void quick_sort(int d[], int left, int right)
{
	if(left < right)
	{
		int mid = get_mid(d, left, right);
		quick_sort(d, left, mid - 1);
		quick_sort(d, mid + 1, right);
	}
}
long kuaisu()
{
	int d[100000] = {0};
	srand(time(NULL));
	for(i = 0; i < 100000; i++)
	{
		d[i] = random();
	}
	long start_kuaishu, end_kuaishu;
	time(&start_kuaishu);
	quick_sort(d, 0, 99999);
	time(&end_kuaishu);
	printf("快速排序前五个数排序：\n");
	for(i = 0; i < 5; i++)
	{
		printf("%d\n",d[i]);
	}
	return end_kuaishu - start_kuaishu;
}
int main()
{
	
	//冒泡排序
	long time_maopao = maopao();
	//选择排序
	long time_xuanzhe = xuanzhe();
	//直接插入排序
	long time_charu = charu();
	//快速排序
	long time_kuaisu = kuaisu();
	printf("十万个数冒泡排序需要%ld秒\n",time_maopao);
	printf("十万个数选择排序需要%ld秒\n",time_xuanzhe);
	printf("十万个数直接插入需要%ld秒\n",time_charu);
	printf("十万个数快速排序需要%ld秒\n",time_kuaisu);
	return 0;
}
